import java.util.HashMap;
import java.util.Map;

public class Solution1255 {

    int max=0;

    public int maxScoreWords(String[] words, char[] letters, int[] score) {
        Map<Character,Integer> map=new HashMap<>();
        for (char letter : letters) {
            map.put(letter,map.getOrDefault(letter,0)+1);
        }
        int[] scores=new int[words.length];
        for (int i=0;i<words.length;i++){
            for (char c : words[i].toCharArray()) {
                scores[i]+=score[c-'a'];
            }
        }
        dfs(words,0,map,scores,0);
        return max;
    }

    private void dfs(String[] words, int k, Map<Character, Integer> map, int[] scores, int nums) {
        if (k==words.length){
            if (nums>max){
                max=nums;
            }
            return;
        }
        dfs(words,k+1,map,scores,nums);
        String target=words[k];
        Map<Character,Integer> m=new HashMap<>(map);
        for (char c : target.toCharArray()) {
            if (!m.containsKey(c) || m.get(c)==0){
                return;
            }
            m.put(c,m.get(c)-1);
        }
        dfs(words,k+1,m,scores,nums+scores[k]);
    }

    public static void main(String[] args) {
        System.out.println(new Solution1255().maxScoreWords(new String[]{"dog","cat","dad","good"},new char[]{'a','a','c','d','d','d','g','o','o'},new int[]{1,0,9,5,0,0,3,0,0,0,0,0,0,0,2,0,0,0,0,0,0,0,0,0,0,0}));
    }
}
